/*
 * Problems No 78

Subsets 

Given a set of distinct integers, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
 * 
 * 思路： 把选取某个元素作为二进制数的0或1. 1为选取，0为不选取。
 *      只需要 0 到 nums.length位的数字即可。
 *      从0到全为1进行循环即可。
 *      
 * 举例：
 * 	[1,3]
 *  使用数字为2位。也就是最大值为3；
 *  循环数字为  0, 1, 10 , 11
 *  故组合为
 *  [], [1], [3], [1, 3]
 */
package com.leetcode.weicl.problems.no78;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * The Class Solution.<br>
 * 
 * @author FNST)WeiCL
 * @version 1.0
 */
public class Solution {
	
	private List<Integer> pickUp(int[] nums, BigInteger i, int len) {
		List<Integer> list = new ArrayList<Integer>();
		if (i.longValue() == 0) {
			return list;
		}
		for (int j = 0; j < len; j++) {
	        if (i.testBit(j)) {
	        	list.add(nums[j]);
	        }
        }
		return list;
	}
	
	private List<Integer> pickUp(int[] nums, long i, int len) {
		List<Integer> list = new ArrayList<Integer>();
		if (i == 0) {
			return list;
		}
		for (int j = 0; j < len; j++) {
	        if ((i & (1 << j)) != 0) {
	        	list.add(nums[j]);
	        }
        }
		return list;
	}
	
    public List<List<Integer>> subsets(int[] nums) {
    	Arrays.sort(nums);
    	// 构造最大数字
    	
    	// 大数字版本
//    	BigInteger bi = new BigInteger("0");
//    	bi = bi.setBit(nums.length);
    	
    	// long版本
    	long bi = 1 << nums.length;
    	
    	List<List<Integer>> ans = new ArrayList<List<Integer>>();
    	// 循环
    	long i = 0;
    	while( i < bi) {
    		ans.add(pickUp(nums, i, nums.length));
    		i++;
    	}
    	// 大数字版本
//    	BigInteger i = BigInteger.ZERO;
//    	while( i.compareTo(bi) < 0) {
//		ans.add(pickUp(nums, i, nums.length));
//		i = i.add(BigInteger.ONE);
//	}
    	
    	return ans;
    }
    
    public static void main(String[] args) {
    	Solution s = new Solution();
	    System.out.println(s.subsets(new int[]{1,2,3,0}));
    }
}
